package hwTwo1;

import java.util.Random;

public class ShellSortTest {

    public static void main(String[] args) {
        int[] sizes = {100, 1000, 10000, 100000, 1000000}; // 数组大小按照10的幂次递增
        for (int size : sizes) {
            Double[] array = generateRandomArray(size); // 生成随机数组
            System.out.println("Array size: " + size);
            shellSort(array);
            System.out.println();
        }
    }

    // 生成随机数组
    public static Double[] generateRandomArray(int size) {
        Random random = new Random();
        Double[] array = new Double[size];
        for (int i = 0; i < size; i++) {
            array[i] = random.nextDouble();
        }
        return array;
    }

    // 希尔排序
    public static void shellSort(Double[] array) {
        int n = array.length;
        int h = 1;
        int totalComparisons = 0; // 总比较次数

        // 计算递增序列初始值
        while (h < n / 3) {
            h = 3 * h + 1; // 使用 Knuth 的递增序列：1, 4, 13, 40, ...
        }

        // 对每个递增序列 h 进行排序
        while (h >= 1) {
            int comparisons = 0; // 当前递增序列的比较次数

            // 插入排序
            for (int i = h; i < n; i++) {
                for (int j = i; j >= h && less(array[j], array[j - h]); j -= h) {
                    exch(array, j, j - h);
                    comparisons++;
                }
            }

            totalComparisons += comparisons;

            // 打印每个递增序列带来的比较次数和数组大小的比值
            System.out.printf("h = %d, comparisons = %d, comparisons/size = %.5f%n",
                    h, comparisons, (double) comparisons / n);

            h /= 3; // 缩小递增序列
        }

        System.out.printf("Total comparisons: %d, comparisons/size = %.5f%n",
                totalComparisons, (double) totalComparisons / n);
    }

    // 比较两个元素的大小
    private static boolean less(Double v, Double w) {
        return v.compareTo(w) < 0;
    }

    // 交换两个元素
    private static void exch(Double[] array, int i, int j) {
        Double temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}